The present invention relates to a security technique for computer networks, and more particularly to a method for generating an elliptic curve used especially for elliptic curve cryptography, an elliptic curve apparatus, an elliptic curve cryptosystem, and a storage medium storing said method.
As an elliptic curve for elliptic curve cryptography, a normal form elliptic curve y2=f(x) may be used, where f(x)=x3+ax+b(a,bxcex5Fp) where Fp is a finite field composed of p elements and p is a large prime number. Each set (x0,y0), where x0,y0xcex5Fp, satisfying the equation y02=f(x0) is called a point on the curve. Operation can be performed in the set of all of these points plus a point at infinity, and the number of the points is called a curve order. When a curve order is denoted by n and expressed as n=cl where c is a positive integer, called a cofactor, and 1 is a large prime number, the elliptic curve is called safe if the value of c is small. In a method for generating a safe normal form elliptic curve, described in ANSI X9.62, xe2x80x9cPublic Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)xe2x80x9d, 1999, a normal form elliptic curve is repeatedly generated at random, and its safety is evaluated based on its curve order until a safe normal form elliptic curve is obtained.
Furthermore, according to xe2x80x9cP. L. Montgomery, Speeding the Pollard and Elliptic Curve Methods of Factorization, Math. Comp. 48 (1987) 243-264xe2x80x9d, by using the Montgomery type elliptic curve By2=X3+AX2+X(A,Bxcex5Fp), operation can be performed at higher speed than by use of a normal form elliptic curve. A normal form elliptic curve can be transformed to a Montgomery type elliptic curve when a point on the normal form elliptic curve corresponds to a point on the Montgomery type elliptic curve, one to one, and operation on one point coincides with operation on the other. Not all of normal form elliptic curves can be transformed to Montgomery type elliptic curves. Requirements for a normal form elliptic curve to be transformable to a Montgomery type elliptic curve are described in a paper entitled xe2x80x9cCalculation Method for Elliptic Curve Cryptographic Operationxe2x80x9d by Tetsuya Izu (1999 Symposium on Cryptography and Information Security, Publication vol. 1, 1999, 275-280). The above paper also discloses that the curve order of each Montgomery type elliptic curve is always divisible by 4.
However, the above conventional technique has given no consideration to generation of a normal form elliptic curve transformable to a Montgomery type elliptic curve. Therefore, to generate a safe normal form elliptic curve transformable to a Montgomery type elliptic curve, it is necessary to generate a safe normal form elliptic curve and then determine whether it is transformable to a Montgomery type elliptic curve, and if not, a safe normal form elliptic curve is generated again and the above procedure must be repeated until a safe normal form elliptic curve transformable to a Montgomery type elliptic curve is found. Generally, a process for generating a safe normal form elliptic curve takes longer time than a process for determining whether it can-be transformed to a Montgomery type elliptic curve. Because of this, generation of an elliptic curve having the above properties requires a large amount of time, making it difficult to regularly replace an elliptic curve with a new elliptic curve having the above properties in elliptic curve cryptography to ensure network security. Incidentally, to ensure security against an attack using the Baby-Step-Giant-Step method in which pre-calculation for the attack can be performed by knowing only the respective elliptic curve without knowing the public key, the elliptic curve must be regularly replaced with a new one, and no other effective methods exist. This means that in the above conventional technique, a specific elliptic curve is easily attacked.
It is an object of the present invention to provide a method, an apparatus, an elliptic curve cryptosystem, and a storage medium for generating an elliptic curve to improve operation speed and security.
To achieve the above object, the present invention provides a method for generating an elliptic curve, comprising the steps of: generating a first elliptic curve, for example, y2=x3+ax+b; determining whether said first elliptic curve can be transformed to a second elliptic curve, for example, BY2=X3+AX2+X; and determining safety of the first elliptic curve transformable to said second elliptic curve. Here, as the first elliptic curve, an elliptic curve defined over a field of a predetermined prime order may be used. Further, said step of determining whether said first elliptic curve can be transformed to said second elliptic curve includes steps of: determining whether there is xcex1 for which f(xcex1)=0 for said first elliptic curve y2=f(x)=x3+ax+b; and determining whether fxe2x80x2(xcex1) has a square root for xcex1 for which f(xcex1)=0. Further, said step of determining the safety of said first elliptic curve includes steps of: extracting information on a curve order of said first elliptic curve; and judging a cofactor based on the information on said curve order. The present invention further provides a method for generating an elliptic curve, comprising the steps of: generating a first elliptic curve y2=x3+ax+b; generating a second elliptic curve y2=x3+ar2x+br3; determining whether said first elliptic curve can be transformed to a third elliptic curve BY2=X3+AX2+X; and when said first elliptic curve can be transformed to said third elliptic curve, judging safety of said first elliptic curve and said second elliptic curve. The present invention provides a method for generating an elliptic curve defined over a prime field in elliptic curve cryptography, comprising the steps of: randomly generating a normal form elliptic curve y2=x3+ax+b; determining whether said generated normal form elliptic curve y2=x3+ax+b can be transformed to a Montgomery type elliptic curve BY2=X3+AX2+X; determining divisibility of a curve order of said elliptic curve by 8; collecting information on the curve order of said elliptic curve; and judging a value of a cofactor based on the information on said curve order; wherein a normal form elliptic curve which can be transformed to a Montgomery type elliptic curve and whose cofactor is 4 is generated. The present invention provides an apparatus for generating an elliptic curve, comprising: elliptic curve candidate generating means for generating a first elliptic curve y2=x3+ax+b; transformability judgement means for determining whether said first elliptic curve can be transformed to a second elliptic curve By2=X3+AX2+X; safety judgement means for determining safety of the first elliptic curve transformable to said second elliptic curve. Here, said transformability judgement means includes: root existence judgement means for determining whether there is xcex1 for which f(xcex1)=0 for said first elliptic curve; and square root judgement means for determining whether fxe2x80x2(xcex1) has a square root for a for which f(xcex1)=0. Alternatively, said transformability judgement means includes: root existence judgement means for determining whether there is xcex1 for which f(xcex1)=0 for said first elliptic curve; and quadratic residue judgement means for determining whether fxe2x80x2(xcex1) is a quadratic residue for xcex1 for which f(xcex1)=0. The present invention provides an apparatus for generating an elliptic curve employed in a cryptosystem in which a first computer and a second computer carry out cryptocommunications with each other, wherein said apparatus receives a request for generation of an elliptic curve from each said computer and generates a normal form elliptic curve transformable to a Montgomery type elliptic curve. The present invention provides a cryptosystem for carrying out cryptocommunications by use of elliptic curve cryptography, comprising: a first computer for receiving cryptocommunication; a second computer for transmitting cryptocommunication; and an elliptic curve generating apparatus for receiving a request for generation of an elliptic curve from said first computer and generating a normal form elliptic curve transformable to a Montgomery type elliptic curve. Further, said cryptosystem further comprises a curve replacement management apparatus for managing whether it is necessary to replace an elliptic curve being used for cryptocommunications, wherein when it becomes necessary to replace said elliptic curve, the elliptic curve is replaced with an elliptic curve newly generated by said elliptic curve generating apparatus to carry out cryptocommunications. It should be noted that to achieve the above object, a storage medium may be used to store programs implementing functions performed by the methods, apparatuses, and systems described above.